package com.hanxiaozhang.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈归并面试题〉
 *
 * @author hanxinghua
 * @create 2021/9/12
 * @since 1.0.0
 */
public class MergeTopic {


    public static void main(String[] args) {
//        int[] array1 = {1, 3, 5, 22, 4};
//        System.out.println(topic1(array1));

        int[] array2 = {3, 1, 7, 0, 2};
        // (3,7) (1,7) (1,2) (0,2)
        topic2(array2);
        System.out.println("-----------");
        int[] array3 = {3, 1, 7, 0, 2};
        // (3,1) (3,2) (1,0) (7,2) (3,0)  (7,0)
        topic3(array3);

    }

    /**
     * 求数组当前顺序中的降序对：举例：[3,1,7,0,2]：
     * (3,1) (3,0) (3,2) (1,0)  (7,0) (7,2)
     *
     * @param array3
     */
    public static void topic3(int[] array3) {
        if (array3 == null || array3.length < 2) {
            return;
        }
        List<Pair<Integer, Integer>> result = new ArrayList<>();
        process_2(array3, 0, array3.length - 1, result);
        if (!result.isEmpty()) {
            result.forEach(x -> System.out.println(x.toString()));
        }
    }


    /**
     * @param array
     * @param L
     * @param R
     * @return
     */
    public static void process_2(int[] array, int L, int R, List<Pair<Integer, Integer>> result) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process_2(array, L, mid, result);
        process_2(array, mid + 1, R, result);
        merge_2(array, L, mid, R, result);
    }


    /**
     * @param array
     * @param L
     * @param M
     * @param R
     * @param result
     * @return
     */
    public static void merge_2(int[] array, int L, int M, int R, List<Pair<Integer, Integer>> result) {

        for (int i = L; i <= M; i++) {
            for (int j = M + 1; j <= R; j++) {
                if (array[i] > array[j]) {
                    result.add(new Pair<>(array[i], array[j]));
                }
            }
        }

    }


    /**
     * 求数组当前顺序中的升序对：举例：[3,1,7,0,2]：
     * (3,7) (1,7) (1,2) (0,2)
     *
     * @param array2
     */
    public static void topic2(int[] array2) {
        if (array2 == null || array2.length < 2) {
            return;
        }
        List<Pair<Integer, Integer>> result = new ArrayList<>();
        process_1(array2, 0, array2.length - 1, result);
        if (!result.isEmpty()) {
            result.forEach(x -> System.out.println(x.toString()));
        }
    }


    /**
     * @param array
     * @param L
     * @param R
     * @return
     */
    public static void process_1(int[] array, int L, int R, List<Pair<Integer, Integer>> result) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process_1(array, L, mid, result);
        process_1(array, mid + 1, R, result);
        merge_1(array, L, mid, R, result);
    }


    /**
     * @param array
     * @param L
     * @param M
     * @param R
     * @param result
     * @return
     */
    public static void merge_1(int[] array, int L, int M, int R, List<Pair<Integer, Integer>> result) {
        for (int i = L; i <= M; i++) {
            for (int j = M + 1; j <= R; j++) {
                if (array[i] < array[j]) {
                    result.add(new Pair<>(array[i], array[j]));
                }
            }
        }
    }


    /**
     * 在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。
     * 例子： [1,3,4,2,5]
     * 1左边比1小的数：没有
     * 3左边比3小的数：1
     * 4左边比4小的数：1、3
     * 2左边比2小的数：1
     * 5左边比5小的数：1、3、4、 2
     * 所以数组的小和为1+1+3+1+1+3+4+2=16
     *
     * @param array
     * @return
     */
    public static int topic1(int[] array) {
        if (array == null || array.length < 2) {
            return 0;
        }
        return process(array, 0, array.length - 1);
    }


    /**
     * array[L..R]既要排好序，也要求小和返回
     *
     * @param array
     * @param L
     * @param R
     * @return
     */
    public static int process(int[] array, int L, int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return process(array, L, mid) + process(array, mid + 1, R) + merge(array, L, mid, R);
    }

    /**
     * 排序，并且比较出最小
     *
     * @param array
     * @param L
     * @param M
     * @param R
     * @return
     */
    public static int merge(int[] array, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        int res = 0;
        while (p1 <= M && p2 <= R) {
            // 如果p1比p2小，则有(R - p2 + 1)个元素小于p2。
            res += array[p1] < array[p2] ? (R - p2 + 1) * array[p1] : 0;
            // 这里是小于，类比mergeSort1()
            help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
        }
        while (p1 <= M) {
            help[i++] = array[p1++];
        }
        while (p2 <= R) {
            help[i++] = array[p2++];
        }
        for (i = 0; i < help.length; i++) {
            array[L + i] = help[i];
        }
        return res;
    }


}

class Pair<K, V> {

    private K k;
    private V v;


    public Pair(K k, V v) {
        this.k = k;
        this.v = v;
    }

    @Override
    public String toString() {
        return "(" + k + ", " + v + ")";
    }

}
